package 第一章基础算法.归并排序.id787归并排序;

import java.util.Scanner;

/**
 *输入格式
 * 输入共两行，第一行包含整数 n。
 * 第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
 *
 * 输出格式
 * 输出共一行，包含 n 个整数，表示排好序的数列。
 */
public class Main {
    public static void main(String[]args){
        //处理输入
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for(int i = 0;i<n;i++){
            nums[i] = scanner.nextInt();
        }
        //归并排序
        mergeSort(nums,0,n-1);
        //处理输出
        for(int num : nums){
            System.out.print(num + " ");
        }
    }

    public static void mergeSort(int[]nums,int l ,int r){
        if(l >= r) return;
        int mid = l + (r-l>>1);
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);

        int[]help = new int[r-l+1];
        int k = 0;
        int p1 = l;
        int p2 = mid+1;

        while (p1 <= mid && p2 <=r){
            if(nums[p1] <= nums[p2]){
                help[k++] = nums[p1++];
            }else
                help[k++] = nums[p2++];
        }
        while (p1 <= mid){
            help[k++] = nums[p1++];
        }
        while (p2 <= r){
            help[k++] = nums[p2++];
        }

        for(int i=0;i<help.length;i++){
            nums[l+i] = help[i];
        }
    }

    public static void swap(int[]nums, int a,int b){
        int x = nums[a];
        nums[a] = nums[b];
        nums[b] = x;
    }
}
